#include <algorithm>
#include <cstdio>
#include <cstring>
const int N = 50001;
int t, a, b, d, cnt;
bool vis[N];
int pri[N], mul[N];
long long sum[N];
int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
	freopen("testdata.in", "r", stdin);
	freopen("testdata.out", "w", stdout);
#endif
#ifndef LOCAL
	freopen("Mobius.in", "r", stdin);
	freopen("Mobius.out", "w", stdout);
#endif
#endif

	scanf("%d", &t);
	mul[1] = 1;
	for (int i = 2; i <= N; ++i) {
		if (!vis[i]) {
			pri[++cnt] = i;
			mul[i] = -1;
		}
		for (int j = 1; j <= cnt && pri[j] * i <= N; ++j) {
			vis[i * pri[j]] = true;
			if (i % pri[j] == 0)
				break;
			else
				mul[i * pri[j]] = -mul[i];
		}
	}
	for (int i = 1; i <= N; ++i) { sum[i] = sum[i - 1] + mul[i]; }
	while (t--) {
		scanf("%d%d%d", &a, &b, &d);
		if (a > b) std::swap(a, b);
		long long ans = 0;
		for (int l = 1, r = 0; l <= a / d; l = r + 1) {
			r = std::min(a / (a / l), b / (b / l));
			ans += (sum[r] - sum[l - 1]) * (a / l / d) * (b / l / d);
		}
		printf("%lld\n", ans);
	}
	return 0;
}